The Internet is a convenient and relatively inexpensive medium for high-speed communication, facilitating information exchange between individuals and organizations across the globe. One of the main means of achieving this type of communication over the Internet is through electronic mail (email), which can easily transport vast amounts of data between parties separated by large distances, almost instantaneously. Because of its convenience and inexpensive nature, email has become a communication staple, not only for correspondence between private individuals, but also for most business entities.
FIG. 1 shows a simplified view of a distributed communication system 100 with various networks interconnected through the Internet 108. Client computers (clients) 114a, 114b, and 114c are connected to local area network (LAN) 112, which is connected to server computer (server) 110. Likewise, clients 124a, 124b, and 124c are connected to LAN 122, which is connected to server 120. Finally, clients 134a and 134b are connected to LAN 132, which is connected to server 130. In turn, servers 110, 120, and 130 are connected to the Internet 108. The Internet 108, which connects the servers, comprises numerous interconnected computers, also known as routers, which pass data along to its destination. Before a source server (i.e., a server from which an email message is being sent) can forward a packet of data to a destination server (i.e., a server toward which an email message is directed), it must figure out the route, or at least the first part thereof, to send the data through. This is done with the help of Domain Name Servers 140, which translate textual Internet addresses into numeric Internet Protocol addresses.
On the Internet, as in any situation where two or more computers need to communicate, communication protocols are used. There is a layering of protocols, such that one protocol provides a most basic connection between two computers, a second protocol handles packets of information transmitted through the first protocol, and so on. Thus, each successive layer deals with information passed on to it from the previous layer, modifying or decoding that information in some way. On the Internet, the first and most basic layer is a network access layer, which facilitates communication between computers on the same LAN. The protocol used in this layer depends on the type of network hardware and setup. The second layer uses the Internet Protocol (IP), which establishes a simple connection between computers on different networks, facilitating communication between them. The third layer is the transport layer, using either Transmission Control Protocol (TCP) or User Datagram Protocol (UDP). This layer breaks up the information to be transmitted into smaller packets and monitors their arrival at the destination, allowing for more efficient transmission. The fourth layer, also called the application layer, provides a framework for high-level communication, including protocols such as File Transfer Protocol (FTP) and Telnet. These protocols can be used directly by the user, unlike the lower-level protocols which are generally hidden from the end-user. The application layer also contains some protocols which are not used as applications, but rather are implemented as parts of applications using a graphical user interface (GUI) or other relatively sophisticated user applications. One such protocol is the Hyper Text Transfer Protocol (HTTP) used in Internet browsers such as Netscape Navigator and Microsoft's Internet Explorer. Internet browsers use HTTP to communicate with servers on the Internet, displaying the data they receive in a graphical format.
The Simple Mail Transfer Protocol (SMTP) is also an application layer protocol usually used as part of a GUI application. Users can create email messages using applications such as Netscape Messenger or Microsoft Outlook, and the application then forwards the message towards its destination using SMTP. It is important to note that SMTP is not actually responsible for delivering mail to its ultimate destination, the recipient email server. Rather, as in FIG. 2, the protocol is a means for transporting email messages from the sending client 204, normally a personal computer or workstation, to the sending email server 208, through LAN 206. The email server contains software implementing SMTP, which allows it to communicate with the email client. Common examples of such software include Microsoft Exchange Server and Netscape Messaging Server. Each message is temporarily stored on the sending server 208, until it is forwarded to the recipient server 258 through the Internet 220. An exchange similar to the client-server interaction in 200 takes place on the recipient side 250, where the client 254 connects to the server 258 through LAN 256, and collects or “downloads” the email messages. Just as the sending server 208 stores messages temporarily before forwarding them to their destination, the recipient server 258 stores each message until it is retrieved by the email client 254.
SMTP provides a detailed set of instructions for communication between the client and the server during a transmission session. FIG. 3 illustrates what an SMTP session 300 normally looks like once a connection has already been established between the two machines (using TCP, for example). The client 302 transmits data to the server 304 piece by piece, awaiting confirmation after each piece is sent. Specifically, after the server informs the client that it is ready for an SMTP transmission by sending a “Server Ready” message 310, the client starts the session by sending a “HELLO” message 312. The server then sends confirmation of the start of the session in the form of a first “OK” message 314. The client then sends the server the email address of the user who created and is sending the email message, in the form of a “MAIL FROM” message 316. Once the server's confirmation in the form of a “Sender OK” message 318 has been received, the client forwards the address of each recipient through a “RCPT TO” message 320. The server then confirms receipt and validity of each address by sending a “Recipient OK” message 322. To indicate to the server that transmission of the list of recipients is complete, the client sends a “DATA” message 324. The server then tells the client to start transmission of the message headers and body by sending a “Send Message” message 326. The client then sends the message, indicating the end of the message body by transmitting a special carriage-return-line-feed (CRLF)-dot-CRLF sequence, as in 328. Upon receipt of this special delimiter, the server stores the message in step 336, and sends to the client a second “OK” message 330 to indicate receipt of the full message. The second “OK” message has the significance of indicating to the client that the server is now responsible for delivering the message to its destination, and the client need not do anything more in this matter. Once the client receives this message, it will send a “QUIT” message 332 to the server, and the server will respond with a “Goodbye” message 334, ending the session.
The forwarding of the message to the recipient(s) 338 can occur at any time after the server sends the second “OK” message 330, and is not dependent on any further communication between the server and the client. This can lead to the problem of message duplication because there is a limit to how long an email client will wait for a server's confirmation after transmitting a message to the server. If the confirmation does not arrive within a predetermined amount of time—say, a minute—the client will “time out” or terminate the connection. There are a variety of reasons why a confirmation may not arrive in a timely fashion, perhaps the most obvious being that the server may be slow due to heavy traffic. In fact, it is possible that a confirmation may never arrive if, for example, the confirmation or the message data itself were lost on the network, or the server was shut down at some point before sending a confirmation.
FIG. 4a represents such a “time-out” situation. In FIG. 4a, communication between the client 302 and the server 304 proceeds normally in steps 310 through 328, which are identical to steps 310 through 328 in FIG. 3, respectively. After receiving the message 328 from the client 302, the server 304 proceeds to store the message in step 436 and send a confirmation in the form of a second “OK” message 430. But in this case the server takes too long to issue the confirmation, and there is a time-out 440 on the client side. As previously noted, the server does not need to receive any more communication from the client in order to forward the message in step 438. Meanwhile, the client has no way of distinguishing between the situation where the message was never received by the server, and one where the confirmation from the server was (or will be) sent but will not be received until well after it is expected to arrive. The client 302 therefore assumes that there was a problem with message delivery to the server 304, and tries to transmit the message again later, as in FIG. 4b. In cases where the server did send a confirmation but simply took too long, the second attempt by the client will result in a duplicate message being sent, as described below.
In FIG. 4b, the client 452 establishes a new session with the server 454, and proceeds to transmit in steps 460 through 478 exactly the same information as was transmitted in FIG. 4a, in steps 310 through 328, respectively. The message stored in step 486 is therefore identical to that stored in step 436, and the transmission of that message in step 488 constitutes a duplicate message being sent. As in step 330, the server sends a second “OK” message in step 480, and the connection is mutually terminated in steps 482 and 484.
There are existing methods for minimizing or perhaps even eliminating the duplicate messaging problem. One approach is to set up the server to process messages and send confirmations quickly, thus reducing the number of timeouts that occur on the client side. While this technique is aimed at reducing unnecessary message duplication, it cannot be relied on to eliminate the problem. Nor is it always a practical solution. A second approach involves checkpointing—assigning a unique identifier to each message, which would allow the client to know whether a previous attempt to transmit a message was successful. While this technique would effectively eliminate the duplication problem, it requires implementation on both the server and client sides, and is in rare use today.